package JoReg

import "fmt"

type TableBuild struct {
	sdKeySymbolMap   map[int]*Symbol
	symbolSlc        []*Symbol
	runFirstSetFlag  bool
	runFollowSetFlag bool
	table            [NO_TERMINAL_MAXRANGE][TERMINAL_MAX_RANGE]int
	productionCount  int
}

func MakeTableBuild() *TableBuild {
	tablePtr := &TableBuild{
		sdKeySymbolMap:   make(map[int]*Symbol),
		symbolSlc:        make([]*Symbol, 0),
		runFirstSetFlag:  true,
		runFollowSetFlag: true,
		productionCount:  0,
	}
	return tablePtr
}

func (this *TableBuild) initProduction() {
	stmt := MakeSymbol(SD_STMT, [][]int{{SD_EXPR, SD_SEMI}}, false)
	this.sdKeySymbolMap[SD_STMT] = stmt
	this.symbolSlc = append(this.symbolSlc, stmt)

	expr := MakeSymbol(SD_EXPR, [][]int{{SD_TERM, SD_EXPR_PRIME}}, true)
	this.sdKeySymbolMap[SD_EXPR] = expr
	this.symbolSlc = append(this.symbolSlc, expr)

	exprPrime := MakeSymbol(SD_EXPR_PRIME, [][]int{{SD_PLUS, SD_TERM, SD_EXPR_PRIME}}, true)
	this.sdKeySymbolMap[SD_EXPR_PRIME] = exprPrime
	this.symbolSlc = append(this.symbolSlc, exprPrime)

	term := MakeSymbol(SD_TERM, [][]int{{SD_FACTOR, SD_TERM_PRIME}}, false)
	this.sdKeySymbolMap[SD_TERM] = term
	this.symbolSlc = append(this.symbolSlc, term)

	termPrime := MakeSymbol(SD_TERM_PRIME, [][]int{{SD_TIMES, SD_FACTOR, SD_TERM_PRIME}}, true)
	this.sdKeySymbolMap[SD_TERM_PRIME] = termPrime
	this.symbolSlc = append(this.symbolSlc, termPrime)

	factor := MakeSymbol(SD_FACTOR, [][]int{{SD_LP, SD_EXPR, SD_RP}, {SD_NUM_OR_ID}}, false)
	this.sdKeySymbolMap[SD_FACTOR] = factor
	this.symbolSlc = append(this.symbolSlc, factor)

	semi := MakeSymbol(SD_SEMI, nil, false)
	this.sdKeySymbolMap[SD_SEMI] = semi
	this.symbolSlc = append(this.symbolSlc, semi)

	plus := MakeSymbol(SD_PLUS, nil, false)
	this.sdKeySymbolMap[SD_PLUS] = plus
	this.symbolSlc = append(this.symbolSlc, plus)

	times := MakeSymbol(SD_TIMES, nil, false)
	this.sdKeySymbolMap[SD_TIMES] = times
	this.symbolSlc = append(this.symbolSlc, times)

	lp := MakeSymbol(SD_LP, nil, false)
	this.sdKeySymbolMap[SD_LP] = lp
	this.symbolSlc = append(this.symbolSlc, lp)

	rp := MakeSymbol(SD_RP, nil, false)
	this.sdKeySymbolMap[SD_RP] = rp
	this.symbolSlc = append(this.symbolSlc, rp)

	numOrId := MakeSymbol(SD_NUM_OR_ID, nil, false)
	this.sdKeySymbolMap[SD_NUM_OR_ID] = numOrId
	this.symbolSlc = append(this.symbolSlc, numOrId)
}

//1.如果A是一个终结符，那么FIRST(A)={A}
//2.对于以下形式的语法推导: s -> A a
//	s是非终结符，A是终结符，a 是零个或多个终结符或非终结符的组合，那么 A 属于 FIRST(s).
//3.对于推导表达式： s -> b a
//  s 和 b 是非终结符，而且b 不是nullable的，那么first(s) = first(b)
//4.对于推导表达式: s -> a1 a2 … an b
//	如果a1, a2 … an 是nullable 的非终结符，b是非终结符但不是nullable的，或者b是终结符，那么 first(s) 是 first(a1)… first(an) 以及first(b)的集合。
func (this *TableBuild) parseFirstSet() {
	for {
		if this.runFirstSetFlag == false {
			break
		}
		this.runFirstSetFlag = false
		for _, symbol := range this.symbolSlc {
			this.addSymbolFirstSet(symbol)
		}
		this.printFirstSet()
	}
}

func (this *TableBuild) addSymbolFirstSet(symbolPtr *Symbol) {
	if isSymbolTerminal(symbolPtr.symVal) {
		return
	}
	for _, productionSlc := range symbolPtr.productionSlcs {
		if isSymbolTerminal(productionSlc[0]) && !isContainer(symbolPtr.firstSet, productionSlc[0]) {
			// 第一个元素是终结符并不在firstSet中
			symbolPtr.firstSet = append(symbolPtr.firstSet, productionSlc[0])
			this.runFirstSetFlag = true
		} else if !isSymbolTerminal(productionSlc[0]) {
			// 第一个元素不是终结符
			for _, production := range productionSlc {
				productionSymbol := this.sdKeySymbolMap[production]
				// 不管第一个元素是不是nullable都会first(s) 包含 first(a), a:第一个元素
				if isContainerAll(symbolPtr.firstSet, productionSymbol.firstSet) == false {
					this.runFirstSetFlag = true
					for _, productionSymbolFirst := range productionSymbol.firstSet {
						if isContainer(symbolPtr.firstSet, productionSymbolFirst) == false {
							symbolPtr.firstSet = append(symbolPtr.firstSet, productionSymbolFirst)
						}
					}
				}
				if !productionSymbol.isNullable {
					break
				}
			}
		}
	}
}

//1.先计算每一个非终结符的first set,并把每个非终结符的follow set设置为空.
//2.对于表达式 s -> …a b…,
//  a 是一个非终结符，b 是终结符或非终结符， 那么FOLLOW(a) 就包含 FIRST(b).
//3.对于表达式 s->…a a1 a2 a3… an b…,
// 	其中a是非终结符，a1, a2 a3… an 是nullable的非终结符，b是终结符或非nullable的非终结符，那么FOLLOW(a) 包含FIRST(a1)… FIRST(an) FIRST(b)的集合。
//4.对于表达式s -> … a
// 	其中a是非终结符，而且a出现在右边推导的最后面，那么FOLLOW(a) 包含 FOLLOW(s)
//5.对于表达式 s -> a a1 a2…an ，
// 	其中a是非终结符而且不是nullable的，a1 a2…an 是nullable的非终结符，那么FOLLOW(a), FOLLOW(a1)…FOLLOW(an) 都包含FOLLOW(s).
func (this *TableBuild) parseFollowSet() {
	this.parseFirstSet()
	for {
		if this.runFollowSetFlag == false {
			break
		}
		this.runFollowSetFlag = false
		for _, symbolPtr := range this.symbolSlc {
			this.addSymbolFollowSet(symbolPtr)
		}
		this.printFollowSet()
	}
}

func (this *TableBuild) addSymbolFollowSet(symbol *Symbol) {
	if isSymbolTerminal(symbol.symVal) {
		return
	}
	for _, productionSlc := range symbol.productionSlcs {
		for i, production := range productionSlc {
			productionSymbol := this.sdKeySymbolMap[production]
			if isSymbolTerminal(productionSymbol.symVal) {
				continue
			}
			for j := i + 1; j < len(productionSlc); j++ {
				followSymbol := this.sdKeySymbolMap[productionSlc[j]]
				productionSymbol.addFollowSet(followSymbol.firstSet, this)
				if followSymbol.isNullable == false {
					break
				}
			}
		}

		pos := len(productionSlc) - 1
		for ; pos >= 0; pos-- {
			previewSymbol := this.sdKeySymbolMap[productionSlc[pos]]
			if isSymbolTerminal(previewSymbol.symVal) == false {
				// 非终结符
				previewSymbol.addFollowSet(symbol.followSet, this)
			}
			if isSymbolTerminal(previewSymbol.symVal) == true && previewSymbol.isNullable == false {
				break
			}
		}
	}
}

//1.计算所以非终结符的first set 和follow set.
//2.对应非nullable的表达式 ,
// 	s -> a b… 其中s是非终结符，a 是一个或多个nullable的非终结符，b是终结符或是非终结符但不是nullable的，b后面可以跟着一系列符号，假设其标号为N,那么该表达式的选择集就是FIRST(a) 和 FIRST(b)的并集。如果a不存在，也就是b的前面没有nullable的非终结符，那么SELECT(N) = FIRST(b).
//3.对应nullable的表达式:
// 	s -> a, s是非终结符，a是零个或多个nullable非终结符的集合，a也可以是ε，假设该表达式标号为N,那么SELECT(N)就是 FIRST(a) 和 FOLLOW(s)的并集。由于a可以是0个非终结符，也就是s -> ε,从而s可以推导为空，如果s推导为空时，那么我们就需要看看当前输入字符是不是FOLLOW(s)，也就是跟在s推导后面的输入字符，如果是的话，我们才可以采用s->ε,去解析当前输入。
func (this *TableBuild) parseSelectionSet() {
	this.parseFollowSet()
	for _, symbolPtr := range this.symbolSlc {
		this.addSymbolSelectionSet(symbolPtr)
	}
}

func (this *TableBuild) addSymbolSelectionSet(symbol *Symbol) {
	if isSymbolTerminal(symbol.symVal) {
		return
	}
	isNullableProduction := true
	for _, productionSlc := range symbol.productionSlcs {
		selectionSlc := make([]int, 0)
		for _, production := range productionSlc {
			currentSymbol := this.sdKeySymbolMap[production]
			if currentSymbol.isNullable == false {
				isNullableProduction = false
				this.addSelectionSet(&selectionSlc, currentSymbol.firstSet)
				break
			}
			this.addSelectionSet(&selectionSlc, currentSymbol.firstSet)
		}
		if isNullableProduction {
			this.addSelectionSet(&selectionSlc, symbol.followSet)
		}
		symbol.selectionSet = append(symbol.selectionSet, selectionSlc)
		isNullableProduction = true
	}
}

func (this *TableBuild) addSelectionSet(selectSet *[]int, set []int) {
	for _, item := range set {
		if isContainer(*selectSet, item) == false {
			*selectSet = append(*selectSet, item)
		}
	}
}

func (this *TableBuild) buildParseTable() {
	this.initBuildTable()
	this.setTable()
	this.printTable()
}

func (this *TableBuild) initBuildTable() {
	for i := 0; i < NO_TERMINAL_MAXRANGE; i++ {
		for j := 0; j < TERMINAL_MAX_RANGE; j++ {
			this.table[i][j] = -1
		}
	}
}

func (this *TableBuild) setTable() {
	for _, symbol := range this.symbolSlc {
		if isSymbolTerminal(symbol.symVal) == true {
			continue
		}
		for _, selectionSlc := range symbol.selectionSet {
			for _, selection := range selectionSlc {
				column := selection
				if column >= TERMINAL_MAX_RANGE {
					column = TERMINAL_MAX_RANGE
				}
				this.table[symbol.symVal-SD_STMT][column] = this.productionCount
			}
			this.productionCount++
		}
	}
}

func (this *TableBuild) printFirstSet() {
	fmt.Println("===================================")
	for _, symbol := range this.symbolSlc {
		if isSymbolTerminal(symbol.symVal) {
			continue
		}
		fmt.Printf("%s => {", getSymbolStr(symbol.symVal))
		for _, first := range symbol.firstSet {
			fmt.Printf("%s ", getSymbolStr(first))
		}
		fmt.Printf("}\n")
	}
}

func (this *TableBuild) printFollowSet() {
	fmt.Println("*******************************")
	for _, symbol := range this.symbolSlc {
		if isSymbolTerminal(symbol.symVal) {
			continue
		}
		fmt.Printf("%s => {", getSymbolStr(symbol.symVal))
		for _, follow := range symbol.followSet {
			fmt.Printf("%s ", getSymbolStr(follow))
		}
		fmt.Printf("}\n")
	}
}

func (this *TableBuild) printTable() {
	for i := 0; i < NO_TERMINAL_MAXRANGE; i++ {
		for j := 0; j < TERMINAL_MAX_RANGE; j++ {
			fmt.Printf("%d ", this.table[i][j])
		}
		fmt.Println()
	}
}

func isContainer(set []int, symbol int) bool {
	if len(set) < 1 {
		return false
	}
	for _, first := range set {
		if first == symbol {
			return true
		}
	}
	return false
}

// isContainerAll 判断firstSet中是否包含checkFirstSet中所有的元素
func isContainerAll(set []int, checkSet []int) bool {
	if len(set) == 0 && len(checkSet) == 0 {
		return true
	}
	if len(set) < len(checkSet) {
		return false
	}
	symbolMap := make(map[int]struct{})
	for _, symbol := range set {
		symbolMap[symbol] = struct{}{}
	}

	for _, checkSymbol := range checkSet {
		if _, ok := symbolMap[checkSymbol]; !ok {
			return false
		}
	}
	return true
}

func isSymbolTerminal(symbol int) bool {
	if symbol < 256 {
		return true
	}
	return false
}
